package 测试;

public class 股票交易日 {

	public static void main(String[] args) {

	}

}

class Stock {
	public int maxProfit(int[] prices, int n) {

		// 第i天前的最大利润
		int[] preMaxProfit = new int[n];
		// 第i天后的最大利润
		int[] afterMaxProfit = new int[n];
		// 总利润
		int maxProfit = Integer.MIN_VALUE;

		int minBuy = prices[0];

		for (int i = 1; i < n; i++) {
			minBuy = Math.min(minBuy, prices[i]);
			preMaxProfit[i] = Math.max(preMaxProfit[i - 1], prices[i] - minBuy);
		}

		int maxSell = prices[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			maxSell = Math.max(maxSell, prices[i]);
			afterMaxProfit[i] = Math.max(afterMaxProfit[i + 1], maxSell - prices[i]);
		}

		for (int i = 0; i < n; i++) {
			maxProfit = Math.max(maxProfit, preMaxProfit[i] + afterMaxProfit[i]);
		}
		return maxProfit;
	}
}